package lcs

type LCS[T comparable] struct {
	a, b []T
	lens [][]int
}

func New[T comparable](a, b []T) *LCS[T] { return &LCS[T]{a: a, b: b} }

func (l *LCS[T]) getLens() [][]int {
	if l.lens == nil {
		lens := make([][]int, len(l.a)+1)
		for i := 0; i <= len(l.a); i++ {
			lens[i] = make([]int, len(l.b)+1)
		}
		// row 0 and column 0 are initialized to 0 already
		for i := 0; i < len(l.a); i++ {
			for j := 0; j < len(l.b); j++ {
				if l.a[i] == l.b[j] {
					lens[i+1][j+1] = lens[i][j] + 1
				} else if lens[i+1][j] > lens[i][j+1] {
					lens[i+1][j+1] = lens[i+1][j]
				} else {
					lens[i+1][j+1] = lens[i][j+1]
				}
			}
		}
		l.lens = lens
	}
	return l.lens
}

func (l *LCS[T]) Len() int {
	if len(l.a) == 0 || len(l.b) == 0 {
		return 0
	}
	return l.getLens()[len(l.a)][len(l.b)]
}

func (l *LCS[T]) Get() []T {
	if len(l.a) == 0 || len(l.b) == 0 {
		return []T{}
	}
	lens := l.getLens()
	// read the substring out from the matrix
	s := make([]T, 0, lens[len(l.a)][len(l.b)])
	for x, y := len(l.a), len(l.b); x != 0 && y != 0; {
		if lens[x][y] == lens[x-1][y] {
			x--
		} else if lens[x][y] == lens[x][y-1] {
			y--
		} else {
			s = append(s, l.a[x-1])
			x--
			y--
		}
	}
	// reverse string
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
	return s
}

func (l *LCS[T]) Similarity() float64 {
	if len(l.a) == 0 || len(l.b) == 0 {
		return 0
	}
	return float64(l.Len()*2) / float64(len(l.a)+len(l.b))
}

type StringLCS LCS[rune]

func String(a, b string) *StringLCS { return (*StringLCS)(New([]rune(a), []rune(b))) }

func (l *StringLCS) Len() int {
	return (*LCS[rune])(l).Len()
}

func (l *StringLCS) Get() string {
	return string((*LCS[rune])(l).Get())
}

func (l *StringLCS) Similarity() float64 {
	return (*LCS[rune])(l).Similarity()
}
